1. Field of the Invention
This invention relates generally to graphical data rendering apparatus and, more specifically to a fast hardware processor for pixel blending and anti-aliasing via area calculation and pixel blending.
2. Discussion of the Related Art
Traditional three-dimensional graphics workstations include simplistic scan conversion hardware that samples points, lines and polygons with a single infinitely-small sample pixel. As a result, the renderings of these graphical primitives show aliasing artifacts. Although increasing monitor pixel density has reduced aliasing effects somewhat, the increase use of motion in modern high-speed workstations has offset this improved aliasing. So the problem of aliasing remains troublesome in all workstation image rendering processors.
Practitioners in the art using contemporary workstations have attempted to solve the aliasing problem using a variety of techniques. Several offer machines that compute proper pixel coverage for points and lines. One example is the accumulation buffer technique proposed by Paul Haeberli, et al ("The Accumulation Buffer: Hardware Support For A High-Quality Rendering", ACM Computer Graphics, Vol. 24, No. 4, pp. 309-318, August 1990). Haeberli, et al propose a polygon anti-aliasing solution that is compatible with existing scan conversion systems while offering high quality and smooth performance/quality tradeoff in lower performance workstation systems. In this technique, the entire image is redrawn into pixel memory many times. Each drawing of the image uses slightly different screen positioning values. The images are averaged in an accumulation buffer to produce a final image, which exhibits anti-aliased properties. The technique is good for points, lines and polygons. It allows simple transparency and can be used for other special effects but is inefficient because it requires multiple drawings.
Loren Carpenter ("The A-Buffer And Anti-Aliased Hidden Surface Method", ACM Computer Graphics, Vol. 18, No. 3, pp. 103-108, July 1984) introduced the A-buffer anti-aliased, area-averaged accumulation buffer technique. The A-buffer is a relatively uncomplicated anti-aliasing mechanism designed to process the vast majority of pixels with minimum effort and maximum precision, spending compute time only on exceptional cases. Accordingly, the fragment intersection approximations used in the technique can run into problems if several surfaces intersect in the same pixel. Also, polygons smaller than bit mask spacing are not properly sampled.
Other practitioners have pursued the approximation table concept introduced by J. Trueblood, et al ("An Efficient Anti-Aliasing Software Algorithm", Society For Information Display International Symposium, San Diego, Session 19, Digest of Technical Papers, Vol. 17, pp. 348-351, May 6-8, 1986). Trueblood, et al propose a software anti-aliasing algorithm that exploits an optical illusion. By controlling the relative intensity of two adjacent pixels, the human eye integrates the light, giving the impression of a single spot whose center is offset toward the brighter of two spots, and whose intensity is equal to the sum of the intensities of the two spots. These sort of anti-aliasing techniques have been used primarily for line and point drawing. The position and orientation relative to the pixel is used to index to a table of elimination values. The value represents the brightness of the line through the pixel. Multiple lines contributing to a pixel are accumulated until a maximum brightness level is obtained. Unfortunately, this brightness approximation technique fails for polygons and does not support transparency.
The problem of correctly sampling, and thus anti-aliasing polygons has been solved many times in many ways. However, the most obvious trend in high-performance workstation graphics processors is toward the capability of rendering many small polygons per second. Recent machines can handle over one million RGB lighted, Gourad-shaded, Z-buffered, connected triangles per second. A second trend is toward improved sampling quality.
These are counter productive trends. Traditional workstation scan conversion system take many shortcuts in arithmetic processing to support the volume of polygon throughput. These shortcuts preclude any sophisticated techniques for eliminating aliasing artifacts arising from non-subpixel positioning (after transformation, vertex coordinates are rounded to the nearest pixel location in an integer screen space), Bresenham sampling (pixels are included in the scan conversion of a polygon based on arithmetic appropriate for a line fill instead of for an area sampling) and sloppy iteration (insufficient accuracy is maintained during edge iteration and the slopes and initial parameter values are not corrected for subpixel locations of vertexes, spans or scans). Although an accurate polygon sampling architecture was introduced as early as 1985 by Henry Fuchs, et al ("Fast Spheres, Shadows, Textures, Transparencies and Image Enhancements in Pixel-Planes", ACM Computer Graphics, Vol. 19, No. 3, pp. 111-120, July 1985), most high-speed graphics processors only recently acquired the processing power correctly address all three of these problems.
Many other practitioners have suggested solutions to the aliasing problem. For instance, in U.S. Pat. No. 5,142,273, Wobermin discloses a symbol generator that blends color through the use of a vertical color blending list representing pixel overlays. Also, in U.S. Pat. No. 5,153,937, Wobermin, et al disclose a similar system for generating anti-aliased video signals. Moreover, in U.S. Pat. No. 5,175,809, Wobermin, et al disclose a pipelined processor employing the pixel sorting and color overlay methods of their earlier disclosures. The pipelining scheme gains the necessary processing power for techniques that would otherwise be too inefficient for rendering applications.
In U.S. Pat. No. 4,930,091, Brian D. Schroeder, et al disclose a triangle classification scheme for three-dimensional graphics display systems that permits automatic disposition of primitive triangle inputs to the rendering engine of a graphics processor. Schroeder, et al use a lookup table to prescreen incoming triangles after computing triangle parameters from the incoming vertexes. The preprocessing frees later processing power.
In U.S. Pat. No. 5,138,699, Barry L. Minor, et al disclose a hardware color interpolator that uses a ray-tracing method for interpolating color value for pixels lying in an area between previously color-imaged pixels. Minor does not consider how to improve processing power and margins.
In U.S. Pat. No. 4,885,688, Carl R. Crawford discloses a system for displaying three-dimensional surface structures using pixel data interpolation. Also, in U.S. Pat. No. 5,070,465, Tetsuro Kato, et al disclose a video image transforming method and apparatus that uses rectangular primitives and interpolates on the resulting triangular sections. Similarly, in U.S. Pat. No. 5,109,481, Olin G. Lathrop, et al disclose a quadratic interpolation technique for shaded image generation that uses quadratic shading based on vertex interpolation in triangular primitives. Finally, in U.S. Pat. No. 5,123,085, Stuart C. Wells, et al disclose a method and apparatus for rendering anti-aliased polygons that relies on a single pass scan conversion process where the pixels at the edges and vertices of the polygon are first determined from the polygon vertex data. Wells, et al accumulate the image at a pixel from the subpixel values associated with each subsequent primitive by compositing each incoming contribution. Through their method, the polygons can be rendered with minimal aliasing without performing the time-consuming process of polygon sorting Z-depth order prior to compositing. Wells, et al do not teach geometric pixel coverage area calculations and their apparatus is limited to a single-layer frame buffer for storing rendered graphics data. The single layer frame buffer prevents effective integration of pixel contributions from multiple polygons and requires time-consuming sorting procedures to support transparency rendering. All of these practitioners strive to push back the processing efficiency boundaries that limit the art.
Other practitioners have proposed improved techniques for rendering the image at each pixel. For instance, in U.S. Pat. No. 4,679,040, Johnson K. Yan discloses a system having a signal modifier circuit for applying a predetermined intensity modification factor to any area not already frozen. Thus, Yan's technique permits the display of areas behind a translucent area having reduced intensity.
In U.S. Pat. No. 4,945,500, Michael F. Deering discloses a triangle processor for three-dimensional graphics display system that compares each pixel during a scan to the polygon to determine whether the pixel is within the polygon. Deering then stores the pixel data according to its relative Z-position and suggests a pipelined procedure for enhanced efficiency in hardware. He reverses the normal polygon overlay process by using "polygon processors" instead of "scan line" pixel processors.
In U.S. Pat. No. 5,142,617, John C. Dalrymple, et al discloses a method and apparatus for tileing a display area defined by lines joining vertexes with a surface normal vector associated with each vertex. Their display area is subdivided into sub-display areas by calculating additional vertexes and surface normal vectors through interpolation. A given sub-display area is rendered by calculating intensity values at its vertexes and tiling its area by linear interpolation of the calculated vertex intensity values.
In U.S. Pat. No. 5,179,638, John F. Dawson, et al discloses a method and apparatus for generating a texture-mapped perspective view that relies on planar polygon vertex interpolation. Thus, anti-aliasing can be accomplished by blurring the portrayal of each polygon edge just enough to reduce the appearance of the "stairstep" aliasing effect but not enough to make the line appear actually fuzzy.
Other schemes attempt to reduce aliasing by weighting the edge-effect on a pixel by the distance of the edge from the geometric center of the pixel so that the color of a polygon edge close to pixel center dominates the pixel. If the edge merely grazes the pixel, then the edge color only minimally affects the pixel color. Also, it is known to compute the contributions of the line or edge on an imaginary set of subpixels having a finer resolution than the actual screen pixel and then rendering the image by accumulating the contributions of the subpixels associated with each actual pixel. The problem of transparency is also pursued by many in the rendering art. Past solutions proposed for the transparency problem include the screen door technique, which is the simplest method in use. A mask is used to select some of the pixels in an object as present and others as missing. It is similar to the screening technique used to print pictures in newspapers. The result appears quite crude on a computer screen. Also, the sorting Z-list technique has been proposed by practitioners in the art for transparency rendering. The primitive objects are first divided into two lists: opaque and transparent. The opaque objects are rendered, usually using a Z-buffer to determine their visibility. The transparent objects are then sorted by distance from the view point and rendered. This technique results in reasonably good images but the separation and sorting operation are very inefficient and slow.
The multipass technique is also useful for transparency rendering although it is primarily used with accumulation buffer rendering techniques described above. An object that is 50% transparent is rendered as opaque in half of the drawings and transparent in the other half, with the final averaged drawing showing a 50% transparent object. The multipass method is slow because of the requirement for multiple drawings and the types of transparency are limited. Only discrete fractional transparency values can be rendered, although increasing the number of passes permits a refined transparency specification at the expense of even slower rendering. The interpolation of transparency values across a polygon is not permitted with this method.
Despite the existence of many sophisticated rendering techniques, most workstation rendering processes are limited to simple methods employing many shortcuts because of limited processing power. Thus, the issue of anti-aliasing requires attention to the precise hardware processing implementation as well as the more general image transformation algorithms and procedures.
Accordingly, the deficiencies and shortcomings of graphic rendering processing techniques are clearly-felt in the art. Specifically, there are clearly-felt needs for methods permitting high-speed hardware implementation of selected combinations of the more sophisticated and computationally intensive anti-aliasing techniques known in the art. Several of these unresolved problems and deficiencies are solved by this invention in the manner described below.